package main

func min(x, y int) int {
	if x < y {
		return x
	}
	return y
}

func minimumTotal(triangle [][]int) int {
	dp := make([][]int, len(triangle))
	result := 1<<31
	for i, row := range triangle {
		dp[i] = make([]int, len(row))
		if i == 0 {
			dp[i][0] = row[0]
			if i == len(triangle) - 1 {
				// last row
				if row[0] < result {
					result = row[0]
				}
			}
		} else {
			for j, v := range row {
				if j == 0 {
					dp[i][j] = dp[i-1][j] + v
				} else if j == len(row) - 1 {
					dp[i][j] = dp[i-1][j-1] + v
				} else {
					dp[i][j] = min(dp[i-1][j-1], dp[i-1][j]) + v
				}
				if i == len(triangle) - 1 {
					// last row
					if dp[i][j] < result {
						result = dp[i][j]
					}
				}
			}
		}
	}
	return result
}

func main() {
	tri := [][]int {
		{2},
		{3, 4},
		{6, 5, 7},
		{4, 1, 8, 3},
	}
	println(minimumTotal(tri))
}